class Solution:
    def fib(self, n: int) -> int:
        if n < 2:return n
        res = [0,1]
        for i in range(n-1):
            res.append((res[-1]+res[-2])%1000000007)
        return res[-1]